package lc20240612;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
  * @description 电话号码的字母组合，回溯算法。
  * @author 不知名帅哥
  * @date 2024/6/12 19:39
  * @version 1.0
*/
public class PhoneNumberCombination {
    public static void main(String[] args) {

        PhoneNumberCombination combination=new PhoneNumberCombination();
        List<String> list = combination.letterCombinations("23");

        System.out.println("list = " + list);
    }

    public final static Map<Character,String> digitToLetters=new HashMap<>();

    static {
        digitToLetters.put('2',"abc");
        digitToLetters.put('3',"def");
        digitToLetters.put('4',"ghi");
        digitToLetters.put('5',"jkl");
        digitToLetters.put('6',"mno");
        digitToLetters.put('7',"pqrs");
        digitToLetters.put('8',"tuv");
        digitToLetters.put('9',"wxyz");
    }

    public List<String> letterCombinations(String digits){
        List<String> combinations=new ArrayList<>();
        if (digits==null||digits.isEmpty()){
            return combinations;
        }
        backTrack("",digits,0,combinations);
        return combinations;
    }

    private void backTrack(String combination, String digits, int i, List<String> combinations) {
        if (i==digits.length()){
            combinations.add(combination);
            return;
        }
        char currentDigit=digits.charAt(i);
        String letters=digitToLetters.get(currentDigit);
        for (char letter : letters.toCharArray()) {
            backTrack(combination+letter,digits,i+1,combinations);
        }
    }
//    public List<String> letterCombinations(String digits) {
//        List<String> res=new ArrayList<>();
//        char[] charArray = digits.toCharArray();
//        for (int i = 0; i < charArray.length; i++) {
//            char c=charArray[i];
//            String temp=digitToLetters.get(c);
//            for (int j = 0; j < temp.length(); j++) {
//                StringBuilder builder = new StringBuilder();
//                builder.append(temp.charAt(j));
//                res.add(j,builder.toString());
//            }
//        }
//        return res;
//    }
}
